package a10_动态规划;

/**
 * <p>
 * a52_回文子串复习1
 * </p>
 *
 * @author flyduck
 * @since 2025/3/6
 */
public class a52_回文子串复习1 {
    //dp[i][j]：表示从i到j的数组是不是回文子串

    //递推公式：
    //chars[i] == chars[j]
    //j - i <= 1
    //dp[i][j] = true
    //result++;
    //dp[i+1][j-1] == true
    //dp[i][j] = true
    //result++;

    //遍历方式：依赖于左下角dp[i+1][j-1]
    //i从大到小  j从小到大

    public int countSubstrings(String s) {
        char[] chars = s.toCharArray();
        int result = 0;

        boolean[][] dp = new boolean[chars.length][chars.length];

        for (int i = chars.length - 1; i >= 0; i--) {
            for (int j = i; j < chars.length; j++) {
                if(chars[i] == chars[j]){
                    if(j-i <= 1){
                        dp[i][j] = true;
                        result++;
                    }else if(dp[i+1][j-1]){
                        dp[i][j] = true;
                        result++;
                    }
                }
            }
        }

        return result;
    }
}
